package com.java.tree;

import org.omg.CORBA.PUBLIC_MEMBER;

import java.util.Arrays;
import java.util.Random;

/**
 * 堆排序
 *
 * @author 19252
 * @date 2020/7/25
 */
public class HeapSort {

    public static void main(String[] args) {
        HeapSort heapSort = new HeapSort();
        int[] array = new int[]{4, 6, 8, 5, 9, - 1, -9, -9};
        heapSort.heapSort(array);
        System.out.println(Arrays.toString(array));

        // 效率测试
        Random random = new Random();
        int[] testArray = new int[80000000];
        for (int i = 0; i < 80000000; i++) {
            testArray[i] = random.nextInt(80000000);
        }
        long millis = System.currentTimeMillis();
        heapSort.heapSort(testArray);
        // System.out.println(Arrays.toString(testArray));
        millis = System.currentTimeMillis() - millis;
        System.out.println("数据排序所需的时间：" + millis + "毫秒");
    }

    /**
     * 编写一个堆排序的方法
     * 数据从小到大排列
     * 使用大顶堆的特性完成
     * 大顶堆的特性：父结点大于两边的子结点
     *
     * @param array 需要被排序的数组
     */
    public void heapSort(int[] array) {
        int length = array.length;
        // 在顺序存储的二叉树中 (n - 1) / 2 即是 索引（取值范围 0 ~ n）为 n 的元素（结点）的 父结点
        // 首先完成一个大顶堆，此时每个父结点都大于两边的子结点
        for (int i = length / 2 - 1; i >= 0; i--) {
            adjustHeap(array, i, length);
        }
        int temp;
        // 长度为 length 的数组就只需要将前面 length - 1 数据排好序，最后的一个自然是排好序的
        // 所以 i = length - 1
        for (int i = length - 1; i > 0; i--) {
            // 将大顶堆的根结点数据，就是数组的第一个数据
            // 将数组的第一个数与最后一个数交换
            temp = array[0];
            array[0] = array[i];
            array[i] = temp;
            // 再次调整，虽然第一个结点的数据置换了
            // 但是第一个结点的两边的子结点的数据依然是剩下的数中最大的两个数
            // 再一次调整只需要与第一个结点的两边的数比较即可
            // i = length 并循环较减小，保证已经排好顺序的数据不再参与排序
            adjustHeap(array, 0, i);
            // 每一次的调整从 0 开始
            // 会保证根结点的两个子结点中一定有一个数是下一次调整需要的最大值
            // 因为每次从 0 开始，如果出现了调整过后根结点小于子结点的情况
            // 就会继续往下调整，直到再次完成大顶堆
        }
    }

    /**
     * 将对应 i 的非叶子节点的数调整成大顶堆
     *
     * @param array  待调整的数组
     * @param i      表示非叶子结点在数组中的索引
     * @param length 表示对多少个元素进行调整，length是在逐渐减小的
     */
    public void adjustHeap(int[] array, int i, int length) {
        // 保存当前结点的值，
        int temp = array[i];
        // 寻找当前结点的左指结点
        for (int k = i * 2 + 1; k < length; k = k * 2 + 1) {
            // 当前结点存在右子结点，并且左子结点大于右子结点
            if (k + 1 < length && array[k] < array[k + 1]) {
                // 那就将指针指向较大的结点
                k++;
            }
            // k 已经经过了数组越界判断在这里就不用了再判断了
            if (array[k] > temp) {
                // 将当前的结点的值变为较大的结点的值
                array[i] = array[k];
                // i 的值变为 k 再次循环的时候就是要判断 k 是否有子结点
                i = k;
            } else {
                // 当前 i 结点下的子树已经完成排序
                break;
            }
        }
        // 如果在循环发生了位置的交换，那此时的 i 即为最后一次交换发生时 k 的位置
        // 再将原先保存的 array[i] 的值 放到原来 array[k] 的位置上 完成数据的交换
        array[i] = temp;
    }
}
